package club.vann.nowcoder;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * <p>难度：Medium</p>
 * <p>题目：设计LRU缓存结构</p>
 * <p>描述：</p>
 * @author vann
 * @program now-coder
 * @description
 * @date 2021-03-09:10:05:18
 */
public class NC93 {
    public static void main(String[] args) {
        NC93 nc93 = new NC93();

        System.out.println("Result["+ Arrays.toString(TestCase.ANS)+"] : " + Arrays.toString(nc93.LRU(TestCase.OPERATORS, TestCase.K)));
    }

    public int[] LRU (int[][] operators, int k) {
        // write code here
        LRUCached lruCached = new LRUCached(k);
        int count = 0;
        for(int[] operator : operators) {
            int ops = operator[0];
            if(ops == 1) {
                // set
                int key = operator[1];
                int val = operator[2];
                lruCached.set(key, val);
            } else if(ops == 2) {
                // get
                int key = operator[1];
                operators[count++][0] = lruCached.get(key);
            }
        }

        int[] ans = new int[count];
        for(int i = 0; i < count; i ++) {
            ans[i] = operators[i][0];
        }
        return ans;
    }

    class LRUCached {
        Map<Integer, Node> map;
        int capacity;
        int size;
        Node head;
        Node tail;

        LRUCached(int capacity) {
            this.capacity = capacity;
            map = new HashMap<>();
            size = 0;
            // 虚拟头/尾节点
            head = new Node(0, 0);
            tail = new Node(-1, -1);
            head.next = tail;
            tail.pre = head;
        }

        void set(int k, int v) {
            // 如果当前容量已经满了，需要删除指定的元素
            if(this.capacity == this.size) {
                this.size --;
                removeLast();
            }
            this.size ++;
            Node node = map.get(k);
            // 判断当前k是否已经存在
            if(node != null) {
                node.v = v;
                moveToHead(node);
            } else {
                node = new Node(k, v);
                addToHead(node);
            }
            map.put(k, node);
        }

        int get(int k) {
            Node node = map.get(k);
            if(node == null) {
                return -1;
            }
            int v = node.v;
            moveToHead(node);
            return v;
        }

        void removeLast() {
            //  没有数据不需要删除
            if(tail.pre == head) {
                return;
            }
            Node node = tail.pre;
            node.pre.next = tail;
            tail.pre = node.pre;
            map.remove(node.k);
        }

        void moveToHead(Node node) {
            node.next.pre = node.pre;
            node.pre.next = node.next;
            addToHead(node);
        }

        void addToHead(Node node) {
            head.next.pre = node;
            node.next = head.next;
            node.pre = head;
            head.next = node;
        }

        class Node {
            int k;
            int v;
            Node pre;
            Node next;

            Node(int key, int val) {
                this.k = key;
                this.v = val;
            }
        }
    }

    static class TestCase {
        public static int[] ANS = {1, -1};
        public static int[][] OPERATORS = {{1, 1, 1}, {1, 2, 2}, {1, 3, 2}, {2, 1}, {1, 4, 4}, {2, 2}};
        public static int K = 3;
    }
}
